package 笔试.未来.two;


import org.junit.Test;

import static MyUtils.MHUtils.can;
import static MyUtils.MHUtils.ptCharShuzu;

public class Main {
    @Test
    public void test() {
        char[][] G ={
                {'X','X','X','O'},
                {'X','O','X','X'},
                {'X','X','O','O'},
                {'O','X','X','O'}
        };
//        char[][] G ={
//                {'X','X','X','O'},
//                {'X','O','X','X'},
//                {'X','X','X','O'},
//        };
        solve(G);
    }


    int n,m;
    char[][] g;
    public void solve(char[][] g) {
        this.g=g;
        n=g.length;m=g[0].length;
        for (int i = 0; i < n; i++) {

            if(g[i][0]=='O')dfs_bhs(i,0);
            if(g[i][m-1]=='O')dfs_bhs(i,m-1);

        }
        for (int j = 0; j < m; j++) {
            if(g[0][j]=='O') dfs_bhs(0,j);
            if(g[n-1][j]=='O')dfs_bhs(n-1,j);
        }

        ptCharShuzu(g);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(g[i][j]=='O'){
                    //只+不-(不回溯
                    dfs2(i,j);
                }
            }
        }
        ptCharShuzu(g);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(g[i][j]=='Z'){
                    g[i][j]='O';
                }
            }
        }
        ptCharShuzu(g);

    }

     int[][] d={
            {-1,0},
            {0,-1},  {0,1},
            {1,0}
    };
    void dfs_bhs(int i, int j) {
        //main没涂色，这里单cur涂，只+(不-
        g[i][j]='Z';

        for (int k = 0; k < 4; k++) {
            int ni= i+d[k][0], nj=j+d[k][1];
            if(ni<0||ni>=n||nj<0||nj>=m||g[ni][nj]=='Z'||g[ni][nj]=='X')continue;

            if(g[ni][nj]=='O')dfs_bhs(ni,nj);
        }
    }
    void dfs2(int i, int j) {
        //main没涂色，这里单cur涂，只+(不-
        g[i][j]='X';

        for (int k = 0; k < 4; k++) {
            int ni= i+d[k][0], nj=j+d[k][1];
            if(ni<0||ni>=n||nj<0||nj>=m||g[ni][nj]=='Z'||g[ni][nj]=='X')continue;

            if(g[ni][nj]=='O')dfs2(ni,nj);
        }
    }
}

